/**
 * 回溯算法
 */
export default class Backtrack {
  /**
   * 全排列问题
   * 输入一段无重复字符的字符串/数字（假定彼此不重复），输出其排列的所有可能性。
   *
   * @param nums {Array<Number|String>} 需要排列的数字列表
   * @param track {Array<Number|String>} 记录排列的路径
   * @param res {Array<Array<Number|String>>}
   * @returns {Array}
   */
  static fullArray(nums, track = [], res = []) {
    // 触发结束条件（为了简化流程，假定排列数字不重复）
    if (nums.length === track.length) {
      res.push(track);
      return res;
    }

    for (let i = 0, num; i < nums.length; i++) {
      num = nums[i]
      // 排除不合法的选项
      if (track.indexOf(num) > -1) continue;
      // 推入路径栈（做选择）
      track.push(num);
      // 进入下一层决策树
      res = Backtrack.fullArray(nums, [...track], res);
      // 弹出路径栈（取消选择、回溯）
      track.pop();
    }

    return res;
  }
}
